#include <stdio.h>

int main()
{
    //int s[] = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
    int s[] = {87, 2, 3, 43, 21, 22, 11, 22, 22, 11, 23, 58};
    int length = sizeof(s) / sizeof(int);
    int l = 0, r = length - 1;
    quick_sort(s, l, r);
    printf("数组排序后的结果为：");
    for(int i = 0; i < length; i++)
    {
        printf("%d ", s[i]);
    }
    return 0;
}

void quick_sort(int s[], int l, int r)
{
    if(l < r)
    {
        int i = l, j = r, x = s[l];
        while(i < j)
        {
            // 从右向左找第一个小于x的数
            while(i < j && s[j] >= x)
                j--;
            if(i < j)
                s[i++] = s[j];
            // 从左向右找第一个大于x的数
            while(i < j && s[i] < x)
                i++;
            if(i < j)
                s[j--] = s[i];
            // 将基准数放置在“中间”位置
            s[i] = x;
            // 左右区间各自递归调用
            quick_sort(s, l, i - 1);
            quick_sort(s, i + 1, r);
        }
    }
}